package zuosheng.stackandQueue;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author lj
 * @Description: 单调栈
 * @date 2020-11-20 11:06
 * @QQ 851477108
 */


public class MonotonicStack {
    public static void main(String[] args){
        int[] arr = {3,4,1,5,6,2,7};
        int[][] res = rightLessWay(arr);
        System.out.println(Arrays.deepToString(res));

        int[][] res1 = getNearLessNoRepeat(arr);
        System.out.println(Arrays.deepToString(res1));
    }

    //O(N)单调栈
    public static int[][] getNearLessNoRepeat(int[] arr){
        //准备一个二维数组和一个栈
        //数组存储的是结果集[左小位置][右小位置]，栈[元素位置]
        int[][] res = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();

        //从左向右for遍历
        for (int i = 0; i < arr.length; i++) {
            //让最小值在栈底，按顺序从下往上升序,在while记录每个数值元素的左右位置的结果
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                //如果arr[i]大于栈顶,将栈顶存放的数组位置的元素弹出
                int popIndex = stack.pop();
                //弹出元素的左小位置，必然是栈下一个的元素
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                //弹出元素的右小位置，必然是需要压入栈的元素，也就是发起while循环的元素
                int rightLessIndex = i;
                //记录res[弹出数值位置[左小0，右小1]]
                res[popIndex][0] = leftLessIndex;
                res[popIndex][1] = rightLessIndex;
            }
            //如果arr[i]值大于栈顶，直接压入
            stack.push(i);
        }

        //最后栈内可能还剩东西，这个while在结算栈中剩余的内容
        //一般会至少还有一个最小值在栈底,当然目前中arr还有[#,#,1,#,#,2,7]，在栈位置是2，4，5
        //与上面一样过程，不过是主动弹出元素，记录元素的结果
        while (!stack.isEmpty()) {
            //弹出栈顶5(值是7)
            int popIndex = stack.pop();
            //弹出元素的左小位置，必然是栈下一个的元素
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            //记录res[弹出数值位置[左小0，右小1]]
            res[popIndex][0] = leftLessIndex;
            //还在栈中的元素的右小必然是-1，因为在他们右边没有比他们更小的数，才会让他们还在栈中
            res[popIndex][1] = -1;
        }
        return res;
    }

    //O(N^2)暴力遍历
    public static int[][] rightLessWay(int[] arr){
        int[][] res = new int[arr.length][2];
        for (int i = 0; i < arr.length; i++){
            int leftLessIndex = -1;
            int rightLessIndex = -1;
            int cur = i - 1;
            while (cur >=0) {
                if (arr[cur] < arr[i]) {
                    leftLessIndex = cur;
                    break;
                }
                cur--;
            }
            cur = i + 1;
            while (cur < arr.length) {
                if (arr[cur] < arr[i]) {
                    rightLessIndex = cur;
                    break;
                }
                cur++;
            }
            res[i][0] = leftLessIndex;
            res[i][1] = rightLessIndex;
        }
        return res;
    }
}
